Primal-dual subgradient methods for minimizing uniformly convex functions

摘要

We discuss non-Euclidean deterministic and stochastic algorithms foroptimization problems with strongly and uniformly convex objectives. We provideaccuracy bounds for the performance of these algorithms and design methodswhich are adaptive with respect to the parameters of strong or uniformconvexity of the objective: in the case when the total number of iterations $N$is fixed, their accuracy coincides, up to a logarithmic in $N$ factor with theaccuracy of optimal algorithms.